#include <ios>
#include <string>
#include <vector>
using namespace std;

void backtrace(vector<string> &res, int left, int right, string &producted) {
  if (left < 0 || right < 0) {
    return;
  }
  if (left == 0 && right == 0) {
    res.push_back(producted);
    return;
  }
  if (left >= right) {
    producted += '(';
    backtrace(res, left - 1, right, producted);
    producted.pop_back();
  } else {
    producted += '(';
    backtrace(res, left - 1, right, producted);
    producted.pop_back();
    producted += ')';
    backtrace(res, left, right - 1, producted);
    producted.pop_back();
  }
}

vector<string> generateParenthesis(int n) {
  // left <= right 只能选择左括号
  int left = n;
  int right = n;
  vector<string> res;
  string producted;
  backtrace(res, left, right, producted);
  return res;
}